
#include <stdio.h>
#include <omp.h>
#include <stdlib.h>
#include <limits.h>
 
#define INF INT_MAX
 
void floydWarshall(int **dist, int v) {
    int i, j, k;
 
    for (k = 0; k < v; k++) {
        for (i = 0; i < v; i++) {
            for (j = 0; j < v; j++) {
                if ((dist[i][k] != INF) && (dist[k][j] != INF) && (dist[i][k] + dist[k][j] < dist[i][j]))
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

int bestDistance(int **dist, int v) {
	int i, j, best = -1;
	int max[v];

	for (i = 0; i < v; i++)
		max[i] = -1;	

	for (i = 0; i < v; i++) {
        for (j = 0; j < v; j++) {
            if ((max[i] < dist[i][j]) || (max[i] == -1))
                max[i] = dist[i][j];
        }

        if ((best > max[i]) || (best == -1))
        	best = max[i];
    }
    return best;
}

void floydWarshallP(int **dist, int v) {
    int i, j, k;
 
    #pragma omp parallel for private(i,j) shared(k) 
    for (k = 0; k < v; k++) {
        for (i = 0; i < v; i++) {
            for (j = 0; j < v; j++) {
                if ((dist[i][k] != INF) && (dist[k][j] != INF) && (dist[i][k] + dist[k][j] < dist[i][j]))
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

int bestDistanceP(int **dist, int v) {   
    int i, j, best = -1;
    int max[v];

    for (i = 0; i < v; i++)
        max[i] = -1;    

    #pragma omp parallel for private(i,j)
    for (i = 0; i < v; i++) {
        for (j = 0; j < v; j++) {
            if ((max[i] < dist[i][j]) || (max[i] == -1))
                max[i] = dist[i][j];
        }

        if ((best > max[i]) || (best == -1))
            best = max[i];
    }
    return best;
}

void printSolutionP(int **dist, int v) {
	int i, j;

    for (i = 0; i < v; i++) {
        for (j = 0; j < v; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

int main(int argc, char const *argv[]) {
	int i, j, op, v, e, m, n, w;
	int **graph;

    if (argc > 1){
        if (atoi(argv[1]) == 0)
            op = 0;
        else if (atoi(argv[1]) == 1)
            op = 1;
        else {
            printf("Uso: t2 [0,1]\n\t1:\tmodo paralelo\n");
            return -1;
        }
    }

    scanf("%d %d", &v, &e);

    graph = (int**)malloc(v * sizeof(int*));
    for (i = 0; i < v; i++)
    	graph[i] = (int*)malloc(v * sizeof(int));    

	for (i = 0; i < v; i++)
		for (j = 0; j < v; j++)
			if (i == j)
				graph[i][j] = 0;
			else
				graph[i][j] = INF;

	for (i = 0; i < e; i++) {
		scanf("%d %d %d", &m, &n, &w);
		graph[m-1][n-1] = w;
        graph[n-1][m-1] = w;
	}

    if (op == 0) {
        floydWarshall(graph, v);
        printf("%d\n", bestDistance(graph, v));
    } else {
        floydWarshallP(graph, v);
        printf("%d\n", bestDistanceP(graph, v));
    }

    for (i = 0; i < v; i++)
    	free(graph[i]);

    free(graph);

    return 0;
}
